###
### Chapter 11: Interpreters
### Charme Interpreter Code
###
### David Evans, March 2009
### Updated for cs1120 Fall 2009, ps7
###
### You should modify this file to answer the questions
### for PS7.  For some of the questions, write your
### answers at the beginning of this file.  For others,
### you will need to find the right places to modify
### in the provided code:
###
###
### Name(s):
###
### Email ID(s):

authors = ['jwb6mz']

### Question 1:

question1 = """
When evalInGlobal("square") is evaluated, the interpretor code checks what
kind of expression it is.  'Square' has earlier been defined as a lambda, so
it will be judged as a NameExpression.  The interpretor code then looks up
'square' in the environment "frame" dictionary and retrieves its value:
a procedure for squaring.  As just a name and not an application, the code will
simply return the procedure, and because the procedure is returned and displayed as
a String, the Python REPL will call the str method of the Procedure object, which
we have defined to display a String similar to what we would get in a Scheme
interpretor.
"""

### Question 2:

charmeFactorialDefinition = "(define factorial (lambda (n) (if (= n 1) 1 (* n (factorial (- n 1))))))"

### Questions 3-8:
### Modify the provided interpreter code below

### Question 9:

pleased = """
I think the class goes at a nice brisk pace and has covered a good bredth of
topics focusing more on programming theory rather than the more purey pragmatic
approach I'm used to.
"""

displeased = """ 
I'm not sure exactly what I mean by this, but it might be good if the lectures
had some interactive element to them other than straight questions.  Sometimes
people seem shy to participate in what may seem like daunting questions.
"""

hopetolearn = """
I would be interested to learn more about how programs interact with each other,
whether it be through code libraries or server-client-type interactions.  It would
also be cool to hear more about the implications of different styles of
computing or programming, where programming is headed in the future and the
potential (or perhaps lack there of) of thing like quantum computing
"""

###
### Charme Interpreter
### This is the code from Chapter 11 of the course book.
###
    
def tokenize(s):
    current = '' 
    tokens = [] 
    for c in s: 
        if c.isspace(): 
            if len(current) > 0: 
                tokens.append(current)
                current = '' 
        elif c in '()': 
            if len(current) > 0: 
                tokens.append(current)
                current = ''
            tokens.append(c) 
        else: 
            current = current + c 
    
    if len(current) > 0: 
        tokens.append(current)
    return tokens 

def parse(s):
    def parsetokens(tokens, inner):
       res = []
       while len(tokens) > 0:
          current = tokens.pop(0)
          if current == '(':
             res.append (parsetokens(tokens, True))
          elif current == ')':
             if inner:
                return res
             else:
                error('Unmatched close paren: ' + s)
                return None
          else:
             res.append(current)
        
       if inner:
          error ('Unmatched open paren: ' + s)
          return None
       else:
          return res

    return parsetokens(tokenize(s), False)

###
### Evaluator
###

def meval(expr, env):
    if isPrimitive(expr):
       return evalPrimitive(expr)
    elif isIf(expr):             
        return evalIf(expr, env)
    elif isCond(expr):
        return evalCond(expr,env)
    elif isDefinition(expr):                
       evalDefinition(expr, env)
    elif isName(expr):
       return evalName(expr, env)
    elif isLambda(expr):
       return evalLambda(expr, env)
    elif isApplication(expr):
       return evalApplication(expr, env)
    else:
       error ('Unknown expression type: ' + str(expr))

### Primitives

def isPrimitive(expr):
    return (isNumber(expr) or isPrimitiveProcedure(expr) or isNull(expr))

def isNumber(expr):
    return isinstance(expr, str) and expr.isdigit()

def isNull(expr):
    return (expr == "null")

def evalPrimitive(expr):
    if isNumber(expr):
        return int(expr)
    elif isNull(expr):
        return None;
    else:
        return expr

def isPrimitiveProcedure(expr):
    return callable(expr)

def primitivePlus (operands):
    if (len(operands) == 0):
       return 0
    else:
       return operands[0] + primitivePlus (operands[1:])

def primitiveTimes (operands):
    if (len(operands) == 0):
       return 1
    else:
       return operands[0] * primitiveTimes (operands[1:])
    
def primitiveMinus (operands):
    if (len(operands) == 1):
       return -1 * operands[0]
    elif len(operands) == 2:
       return operands[0] - operands[1]
    else:
       evalError('- expects 1 or 2 operands, given %s: %s' % (len(operands), str(operands)))

def primitiveEquals (operands):
    checkOperands (operands, 2, '=')
    return operands[0] == operands[1]

def primitiveZero (operands):
    checkOperands (operands, 1, 'zero?')
    return operands[0] == 0

def primitiveGreater (operands):
    checkOperands (operands, 2, '>')
    return operands[0] > operands[1]

def primitiveLessThan (operands):
    checkOperands (operands, 2, '<')
    return operands[0] < operands[1]

### My new primatives for Lists, <=, etc.
def primitiveLessThanEquals (operands):
    checkOperands (operands, 2, '<=')
    return operands[0] <= operands[1]

def primativeCons (operands):
    checkOperands (operands, 2, 'cons')
    return Cons(operands[0], operands[1])

def primativeCar (operands):
    checkOperands (operands, 1, 'car')
    return Cons.getFirst(operands[0])

def primativeCdr (operands):
    checkOperands (operands, 1, 'cdr')
    return Cons.getSecond(operands[0])

def primativeNullTest(operands):
    checkOperands (operands, 1, 'null?')
    return (operands[0] == None)

def primativeList(operands):
    if (len(operands) == 0):
        return None
    else:
        last = None
        for i in range(1, len(operands)):
            last = Cons(operands[i*-1:][0],last)
        return Cons(operands[0],last)
    
def checkOperands(operands, num, prim):
    if (len(operands) != num):
       evalError('Primitive %s expected %s operands, given %s: %s' 
                 % (prim, num, len(operands), str(operands)))

### Special Forms
       
def isSpecialForm(expr, keyword):
    return isinstance(expr, list) and len(expr) > 0 and expr[0] == keyword

def isIf(expr):
    return isSpecialForm(expr, 'if')

def evalIf(expr,env):
    assert isIf(expr)
    if len(expr) != 4:
        evalError ('Bad if expression: %s' % str(expr))
    if meval(expr[1], env) != False:
        return meval(expr[2],env)
    else:
        return meval(expr[3],env)

## Code for Cond Special Form
def isCond(expr):
    return isSpecialForm(expr, 'cond')

def evalCond(expr,env):
    assert isCond(expr)
    for c in expr[1:]:
        if len(c) < 2:
            evalError ('Bad cond expressoin: %s' % str(c))
        else:
            if meval(c[0],env) != False:
                return meval(c[1],env)
    return None
    
### Definitions and Names

class Environment:
    def __init__(self, parent):
        self._parent = parent
        self._frame = {}
    def addVariable(self, name, value):
        self._frame[name] = value
    def lookupVariable(self, name):
        if self._frame.has_key(name):
            return self._frame[name]
        elif (self._parent):
            return self._parent.lookupVariable(name)
        else:
            evalError('Undefined name: %s' % (name))

def isDefinition(expr):
    return isSpecialForm(expr, 'define')

def evalDefinition(expr, env):
    assert isDefinition(expr)
    if len(expr) != 3:
        evalError ('Bad definition: %s' % str(expr))
    name = expr[1]
    if isinstance(name, str):
        value = meval(expr[2], env)
        env.addVariable(name, value)
    else:
        evalError ('Bad definition: %s' % str(expr))

def isName(expr):
    return isinstance(expr, str)

def evalName(expr, env):
    assert isName(expr)
    return env.lookupVariable(expr)

### Procedures

class Procedure:
    def __init__(self, params, body, env):
        self._params = params
        self._body = body
        self._env = env
    def getParams(self):
        return self._params
    def getBody(self):
        return self._body
    def getEnvironment(self):
        return self._env        
    def __str__(self):
        return '<Procedure %s / %s>' % (str(self._params), str(self._body))

def isLambda(expr):
    return isSpecialForm(expr, 'lambda')

def evalLambda(expr,env):
    assert isLambda(expr)
    if len(expr) != 3:
        evalError ('Bad lambda expression: %s' % str(expr))
    return Procedure(expr[1], expr[2], env)

### Applications

def storeReturn(expr, result):
    evalHistory[str(expr)] = result
    return result

def isApplication(expr): # requires: all special forms checked first
    return isinstance(expr, list)
   
def evalApplication(expr, env):
    subexprs = expr
    subexprvals = map (lambda sexpr: meval(sexpr, env), subexprs)
    return mapply(subexprvals[0], subexprvals[1:])

def mapply(proc, operands):
    if (isPrimitiveProcedure(proc)):
        return proc(operands)
    elif isinstance(proc, Procedure):
        if ((str(proc)+str(operands)) in evalHistory):
            return evalHistory[str(proc)+str(operands)]
        else:
            params = proc.getParams()
            newenv = Environment(proc.getEnvironment())
            if len(params) != len(operands):
                evalError ('Parameter length mismatch: %s given operands %s'
                        % (str(proc), str(operands)))
            for i in range(0, len(params)):
                   newenv.addVariable(params[i], operands[i])        
            return storeReturn(str(proc)+str(operands),meval(proc.getBody(), newenv))        
    else:
        evalError('Application of non-procedure: %s' % (proc))

### Eval-Loop

def initializeGlobalEnvironment():
    global globalEnvironment
    global evalHistory
    evalHistory = {}
    globalEnvironment = Environment(None)
    globalEnvironment.addVariable('true', True)
    globalEnvironment.addVariable('false', False)
    globalEnvironment.addVariable('+', primitivePlus)
    globalEnvironment.addVariable('-', primitiveMinus)
    globalEnvironment.addVariable('*', primitiveTimes)
    globalEnvironment.addVariable('=', primitiveEquals)
    globalEnvironment.addVariable('zero?', primitiveZero)
    globalEnvironment.addVariable('>', primitiveGreater)
    globalEnvironment.addVariable('<', primitiveLessThan)
    ### My additions
    globalEnvironment.addVariable('<=', primitiveLessThanEquals)
    globalEnvironment.addVariable('cons', primativeCons)
    globalEnvironment.addVariable('cdr', primativeCdr)
    globalEnvironment.addVariable('car', primativeCar)
    globalEnvironment.addVariable('null?', primativeNullTest)
    globalEnvironment.addVariable('list', primativeList)

def evalError(msg): # not in book
    print "Error: " + msg    

def parseError(msg): # not in book
    print "Parse Error: " + msg    

def evalLoop():
    initializeGlobalEnvironment()
    while True:
        inv = raw_input('Charme> ')
        if inv == 'quit': break
        for expr in parse(inv):
            print str(meval(expr, globalEnvironment))

def evalInGlobal(expr):
    return meval(parse(expr)[0], globalEnvironment)

### Lists

class Cons:
    def __init__(self, firstVal, secondVal):
        self._first = firstVal
        self._second = secondVal
    def getFirst(self):
        return self._first
    def getSecond(self):
        return self._second
    def strReturn(self): ###Returns strings for all connected cons' to print a list in the conventional way
        if (self._second == None):
            return str(self._first)
        else:
            return str(self._first) + " " + self._second.strReturn()            
    def __str__(self):
        if (ListTest(self)):
             return '(' + Cons.strReturn(self)+ ')'
        else:
            return '(%s . %s)' % (str(self._first), str(self._second))

def ListTest(cons):
    if (cons == None):
        return True
    elif isinstance(cons, Cons):
        return ListTest(cons.getSecond())
    else:
        return False
    
